package cn.aylog.example;

import java.util.Arrays;

/**
 * KMP算法匹配字符
 */
public class StringMatch {
    public static void main(String[] args) {
        // int[] next = createNext("agctagcagctagctg");
        // System.out.print("部分字符匹配表 [");
        // for(int i=0; i<next.length; i++) {
        //     System.out.print(i + ", ");
        // }
        // System.out.println("]");
        // System.out.println("部分字符匹配表 " + Arrays.toString(next));

        String str1 = "ABCD ABACCSD";
        String str2 = "CC";
        // int index = KMPMatch(str1, str2, next);
        int index = KMPMatch(str1, str2);
        System.out.println("index = " + index);
    }

    public static int KMPMatch(String str1, String str2) {
        int[] next = createNext(str2);
        return KMPMatch(str1, str2, next);
    }

    /**
     * 使用kmp算法进行字符串匹配
     * @param str1 原字符串
     * @param str2 目标字符串
     * @param next 目标字符串的部分匹配表
     * @return 返回目标字符串第一次出现的位置,否组返回-1
     */
    public static int KMPMatch(String str1, String str2, int[] next) {
        int len2 = str2.length();
        for(int x = 0, y=0; x<str1.length(); x++) {

            while(y>0 && str1.charAt(x) != str2.charAt(y)) {
                y = next[y-1];
            }

            if(str1.charAt(x) == str2.charAt(y)) {
                y++;
            }
            if(y == len2) {
                return x - len2 + 1;
            }
        }
        return -1;
    }

    /**
     * 生成部分字符匹配表
     * @param dst 待查找的目标字符
     * @return 返回部分字符匹配表
     */
    public static int[] createNext(String dst) {
        int len = dst.length();
        int[] next = new int[len];
        // 只有一个字符,长度为0
        next[0] = 0;
        for(int i=1, y=0; i<len; i++) {

            while(y>0&&dst.charAt(i) != dst.charAt(y)) {
                y = next[y-1];
            }

            if(dst.charAt(i) == dst.charAt(y)) {
                y++;
            }
            next[i] = y;
        }
        return next;
    }
}
